package own.stu.jobgib.playown.alg.solution.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BackTrack {

    public static void main(String[] args) {
        BackTrack b = new BackTrack();
//        System.out.println(b.numberOfPatterns(3, 3));
        System.out.println(b.numberOfPatterns(3, 6));

    }

    /**
     * 909 · Android解锁模式
     * 描述
     * 给定一个Android 3x3锁定屏幕和两个整数m和n,其中1≤m≤n≤9,统计可以解锁Android锁定屏幕所有有效模式的总数,包括最少的m个键和最多n个键。
     * 有效模式的规则:
     * 每个模式必须连接至少m个键和最多n个键。
     * 所有的键都必须是不同的。
     * 如果在模式中连接两个连续键的行通过任何其他键，则其他键必须在模式中选择。不允许跳过非选择键。
     * 钥匙的顺序很重要。
     * <p>
     * 样例1
     * <p>
     * 输入: m = 1, n = 1
     * 输出: 9
     */
    public int numberOfPatterns(int m, int n) {
        if (m <= 0 || n <= 0 || m > n) {
            return 0;
        }
        this.m = m;
        this.n = n;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < starts.size(); i++) {
            List<Integer> list = new ArrayList<>();
            list.add(starts.get(i));

            ans.add(0);

            boolean[] visit = new boolean[10];
            visit[starts.get(i)] = true;

            numberOfPatternsHelper(ans, i, list, visit);
        }
        return ans.get(0) * 4 + ans.get(1) * 2 + ans.get(2) * 2 + ans.get(3);
    }

    private void numberOfPatternsHelper(List<Integer> ans, int ansIdx, List<Integer> path, boolean[] visit) {
        if (path.size() >= m && path.size() <= n) {
            ans.set(ansIdx, ans.get(ansIdx) + 1);
        }
        if (path.size() > n) {
            return;
        }
        for (int i = 1; i <= 9; i++) {
            if (visit[i]) {
                continue;
            }
            if (path.size() > 0) {
                Integer pre = path.get(path.size() - 1);
//                if (!canMove(pre, i, visit)) {
                if (map[pre] == map[i] && !visit[(pre + i) / 2]) {
                    continue;
                }
            }
            path.add(i);
            visit[i] = true;
            numberOfPatternsHelper(ans, ansIdx, path, visit);
            path.remove(path.size() - 1);
            visit[i] = false;
        }
    }

    private boolean canMove(int pre, int i, boolean[] visit) {
        if (map[pre] != map[i]) {
            return true;
        }
        if (!visit[(pre + i) / 2]) { // 这个技巧很牛
            return false;
        }
        return true;
    }

    List<Integer> starts = Arrays.asList(1, 2, 4, 5);
    int m, n;
//    int num = 0;

    /*
    | 1 | 2 | 3 |
    | 4 | 5 | 6 |
    | 7 | 8 | 9 |
    1, 3, 7, 9 有对称效果，1可以连接 2，4，5，6，8
    2，8 对称，2可以连接 1，4，7，9，6，3
    同理 4，6
     */
    static int[] map = new int[10];

    static {
        map[1] = 1;
        map[3] = 1;
        map[7] = 1;
        map[9] = 1;

        map[2] = 2;
        map[8] = 2;

        map[4] = 3;
        map[6] = 3;

        map[5] = 4;
    }

    /**
     * 779 · 广义缩写 （lintcode)
     * word 的所有“缩写”的函数（给出任意一种排列即可）
     * <p>
     * 缩写后两个数字之间不能相邻
     * 例1:
     * 输入:
     * word = "word",
     * 输出:
     * ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
     */
    public List<String> generateAbbreviations(String word) {
        // Write your code here
        List<String> ans = new ArrayList<>();
        if (word == null || word.length() == 0) {
            return ans;
        }

        char[] wc = word.toCharArray();

        // 将题意转换为位运算 (ABC)[000] => A1C[010]
        generateAbbreviationsHelper(ans, 0, wc, new byte[wc.length]);

        return ans;
    }

    private void generateAbbreviationsHelper(
            List<String> ans, int startIdx, char[] wc, byte[] res) {
        if (startIdx > wc.length) {
            return;
        }
        ans.add(toStr(wc, res));

        for (int i = startIdx; i < wc.length; i++) {
            res[i] = 1;
            generateAbbreviationsHelper(ans, i + 1, wc, res);
            res[i] = 0;
        }
    }

    private String toStr(char[] wc, byte[] bits) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < wc.length) {
            if (bits[i] == 0) {
                sb.append(wc[i++]);
            } else {
                int j = 1;
                while (i + 1 < wc.length && bits[i + 1] == 1) {
                    j++;
                    i++;
                }
                sb.append(j);
                i++;
            }
        }
        return sb.toString();
    }
}
